package cuppics;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.SortedMap;
import java.util.Map.Entry;
import java.util.TreeMap;

import org.junit.Test;

public class Prj21 {

	/**
	 * Let d(n) be defined as the sum of proper divisors of n (numbers less than
	 * n which divide evenly into n). If d(a) = b and d(b) = a, where a ≠ b,
	 * then a and b are an amicable pair and each of a and b are called amicable
	 * numbers.
	 * 
	 * For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22,
	 * 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1,
	 * 2, 4, 71 and 142; so d(284) = 220.
	 * 
	 * Evaluate the sum of all the amicable numbers under 10000.
	 * 
	 * @throws Exception
	 */
	@Test
	public void test() throws Exception {
		System.out.println(Calculator.calculate(10000));
	}

	public static class Calculator {

		public static int calculate(int upLimit) {

			TreeMap<Integer, Integer> dataMap = new TreeMap<Integer, Integer>();

			// 1, 2 , 3,
			for (int i = 4; i < upLimit; i++) {

				int sum = sumAllDivisors(getAllDivsors(i));
				dataMap.put(i, sum - i);
			}

			for (int i = 4; i < upLimit; i++) {

				int mapTo = dataMap.get(i);

				if (mapTo == i || !dataMap.containsKey(mapTo)
						|| dataMap.get(mapTo) != i) {
					dataMap.remove(i);
				}
			}

			int sum = 0;
			for (Integer div : dataMap.keySet()) {
				sum += div;
			}

			// System.out.println(print_Map(dataMap));

			return sum;

		}

		/**
		 * more simple method  use
		 * Sigma(p^n) = [p^(n+1)]-1/(p-1)
		 * @param divisors
		 * @return
		 */
		public static int sumAllDivisors(List<Integer> divisors) {
			int sum = 0;
			for (Integer i : divisors) {
				sum += i;
			}
			return sum;
		}

		public static List<Integer> getAllDivsors(int num) {

			List<Integer> primeList = new ArrayList<Integer>();

			IntegerDivisor div = new IntegerDivisor();
			div.divisor(num);

			try {
				Calculator.iterList(primeList, div.primeMap);
			} catch (Exception e) {
				e.printStackTrace();
			}

			int sum = 1;
			for (Entry<Long, Integer> entry : div.primeMap.entrySet()) {
				sum *= (entry.getValue() + 1);
			}

			assert (primeList.size() == sum);

			// System.out.println(sum);
			// print_List(primeList);

			return primeList;
		}

		/**
		 * 迭代获取所有因子
		 * @param divisorList
		 * @param primeMap
		 * @throws Exception
		 */
		public static void iterList(List<Integer> divisorList,
				Map<Long, Integer> primeMap) throws Exception {

			// empty
			if (primeMap.keySet().size() == 0) {
				return;
			}

			// one
			if (primeMap.keySet().size() == 1) {

				for (Entry<Long, Integer> entry : primeMap.entrySet()) {
					Long prime = entry.getKey();

					for (int i = 0; i <= entry.getValue(); i++) {
						divisorList.add((int) Math.pow(prime, i));
					}
				}

				return;
			}

			if (primeMap.keySet().size() <= 1)
				throw new Exception("iter error !!!");

			assert (primeMap.keySet().size() > 1);

			for (Entry<Long, Integer> entry : primeMap.entrySet()) {
				Long prime = entry.getKey();
				int times = entry.getValue();

				List<Integer> tmp = new ArrayList<Integer>();

				Map<Long, Integer> primeMapCopy = copyMapExceptKey(primeMap,
						prime);

				for (int i = 0; i <= times; i++) {

					List<Integer> iterRemoveThisPrime = new ArrayList<Integer>();

					iterList(iterRemoveThisPrime, primeMapCopy);

					for (int iter = 0; iter < iterRemoveThisPrime.size(); iter++) {
						tmp.add((int) (Math.pow(prime, i) * iterRemoveThisPrime
								.get(iter)));
					}

				}

				copyArrs(tmp, divisorList);

			}

			return;

		}

		private static Map<Long, Integer> copyMapExceptKey(
				Map<Long, Integer> primeMap, Long prime) {

			HashMap<Long, Integer> ret = new HashMap<Long, Integer>(primeMap);
			ret.remove(prime);

			return ret;
		}

		private static void copyArrs(List<Integer> tmp,
				List<Integer> divisorList) {

			divisorList.clear();
			divisorList.addAll(tmp);

		}

	}

	/**
	 * 因子分解
	 * @author 1440
	 *
	 */
	public static class IntegerDivisor {

		public Map<Long, Integer> primeMap = new HashMap<Long, Integer>();
		public List<Long> primeList = new ArrayList<Long>();

		public void clear() {
			primeMap.clear();
			primeList.clear();
		}

		public void divisor(long num) {

			if (num <= 1)
				return;

			long prime = getPrime(
					num,
					primeList.size() == 0 ? 2
							: primeList.get(primeList.size() - 1));
			if (prime < 0) {
				primeMap.put(num, 1);
				primeList.add(num);
				return;
			} else {

				primeList.add(prime);
				int count = 0;
				do {

					count += 1;
					num = num / prime;
				} while (num % prime == 0);

				primeMap.put(prime, count);

				divisor(num);

			}

		}

		private long getPrime(long num, long start) {

			for (long i = start; i <= Math.sqrt(num); i++) {
				if (num % i == 0) {
					return i;
				}
			}
			return -1;
		}

		@Override
		public String toString() {

			return print_Map(this.primeMap);
		}

		public Long getLargestPrime() {
			return primeList.get(primeList.size() - 1);
		}

	}

	public static String print_Map(Map<?, ?> primeMap) {
		StringBuilder sb = new StringBuilder();
		for (Entry<?, ?> entry : primeMap.entrySet()) {
			sb.append(entry.getKey().toString() + "="
					+ entry.getValue().toString() + "\n");
		}
		return sb.toString();
	}

	public static void print_List(List<Integer> list) {
		for (int i = 0; i < list.size(); i++) {
			System.out.print(list.get(i) + ",");
		}
		System.out.println();
	}

}
